Balanced binary tree

Time: O(N); Space: O(H); easy

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as:

a binary tree in which the left and right subtrees of every node differ in height by no more than 1.

Example 1:

Input: root = {TreeNode} [3,9,20,None,None,15,7]

  3
 / \
9  20
  /  \
 15   7

Output: True

Example 2:

Input: root = {TreeNode} [1,2,2,3,3,None,None,4,4]

      1
     / \
    2   2
   / \
  3   3
 / \
4   4

Output: False

Explanation:

  • The height of node 1’s right sub-tree is 1 but left sub-tree is 3.

[1]:

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

[2]:

class Solution1(object):
    """
    Time: O(N)
    Space: O(H), H is height of Binary Tree
    """
    def isBalanced(self, root):
        """
        :type root: TreeNode
        :rtype: boolean
        """
        def getHeight(root):
            if root is None:
                return 0
            left_height, right_height = getHeight(root.left), getHeight(root.right)

            if left_height < 0 or right_height < 0 or abs(left_height - right_height) > 1:
                return -1
            return max(left_height, right_height) + 1

        return (getHeight(root) >= 0)

[3]:

s = Solution1()

root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
assert s.isBalanced(root) == True

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(2)
root.left.left = TreeNode(3)
root.left.right = TreeNode(3)
root.left.left.left = TreeNode(4)
root.left.left.right = TreeNode(4)
assert s.isBalanced(root) == False